﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Jenvin.Library.DataStruct
{
    /// <summary>
    /// avl Tree
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class BTreeSet<T>:ICollection<T>
    {
        private const int LH = 1;//左高
        private const int EH = 0;//等高
        private const int RH = -1;//右高
        private Node m_root = null;
        private IComparer<T> m_comparer = null;
        private int m_count = 0;
        internal sealed class Node
        {
            public T Item;

            public Node Left;

            public Node Right;
            /// <summary>
            /// 平衡因子 
            /// </summary>
            public int BF;

            //public override bool Equals(object obj)
            //{
            //    if (this == obj)
            //        return true;
            //    if (obj == null)
            //        return false;
            //    if (obj.GetType() != this.GetType())
            //        return false;


            //    ///return base.Equals(obj);
            //}
        }
        internal class DelegateComparer<T1> : IComparer<T1>
        {
            private Comparison<T1> m_comparison = null;
            public DelegateComparer(Comparison<T1> comparison)
            {
                if (comparison == null)
                    throw new ArgumentNullException("comparison");
                this.m_comparison = comparison;
            }

            #region IComparer<T> 成员

            public int Compare(T1 x, T1 y)
            {
                return m_comparison(x, y);
            }

            #endregion
        }

        public BTreeSet()
            : this((IComparer<T>)null)
        {

        }

        public BTreeSet(Comparison<T> comparison)
            : this(new DelegateComparer<T>(comparison))
        {

        }
        public BTreeSet(IComparer<T> comparer)
        {
            if (comparer == null || comparer == Comparer<T>.Default)
                m_comparer = Comparer<T>.Default;
            else
                m_comparer = comparer;
        }
        public bool Add(T item)
        {
            bool taller = false;
            bool success= Insert(ref m_root, item, out taller);
            if (success)
            {
                this.m_count++;
            }
            return success;
        }

        public bool Remove(T item)
        {
            bool shorter = false;
            bool success= Delete(ref m_root, item, out shorter);
            if (success)
                this.m_count--;
            return success;
        }
        /// <summary>
        /// 右旋
        /// </summary>
        /// <param name="p"></param>
        private void RRotate(ref Node p)
        {
            Node lc = p.Left;
            p.Left = lc.Right;
            lc.Right = p;
            p = lc;
        }
        /// <summary>
        /// 左旋
        /// </summary>
        /// <param name="p"></param>
        private void LRotate(ref Node p)
        {
            Node rc = p.Right;
            p.Right = rc.Left;
            rc.Left = p;
            p = rc;
        }
        /// <summary>
        /// 插入用的左平衡
        /// </summary>
        /// <param name="tNode"></param>
        private void LeftBalance(ref Node tNode)
        {
            Node lc = tNode.Left;
            switch (lc.BF)
            {
                //参看 AVL树图解.vsd LeftBalance case A
                case LH:
                    tNode.BF = lc.BF = EH;
                    RRotate(ref tNode); break;

                case RH:
                    Node rd = lc.Right;
                    switch (rd.BF)
                    {
                        // 参看 AVL树图解.vsd LeftBalance case B.1
                        case LH: tNode.BF = RH; lc.BF = EH; break;
                        //参看 AVL树图解.vsd LeftBalance case B.2
                        case EH: tNode.BF = lc.BF = EH; break;
                        //参看 AVL树图解.vsd LeftBalance case B.3
                        case RH: tNode.BF = EH; lc.BF = LH; break;
                    }
                    rd.BF = EH;//rd 为根
                    LRotate(ref tNode.Left);
                    RRotate(ref tNode);
                    break;
                default:
                    break;
            }
        }
        /// <summary>
        /// 删除用的左平衡
        /// </summary>
        /// <param name="tNode"></param>
        /// <param name="shorter"></param>
        private void LeftBalance(ref Node tNode, out bool shorter)
        {
            Node lc = tNode.Left;
            shorter = true;
            switch (lc.BF)
            {
                case EH:
                    shorter = false;
                    //lc.BF = RH; tNode.BF = RH;
                    tNode.BF = LH; lc.BF = RH;
                    RRotate(ref tNode); break;
                case LH:
                    tNode.BF = lc.BF = EH;
                    RRotate(ref tNode); break;
                case RH:
                    Node rd = lc.Right;
                    switch (rd.BF)
                    {
                        case EH:
                            tNode.BF = EH; lc.BF = EH;
                            break;
                        case LH:
                            tNode.BF = RH; lc.BF = EH;
                            break;
                        case RH:
                            tNode.BF = EH; lc.BF = LH;
                            break;
                    }
                    rd.BF = EH;
                    LRotate(ref tNode.Left);
                    RRotate(ref tNode);
                    break;
            }
        }

        //private void LeftBalance(ref Node tNode, out bool shorter)
        //{
        //    Node lc = tNode.Left;
        //    switch (lc.BF)
        //    {
        //        case RH:
        //            tNode.BF = lc.BF = EH;
        //            RRotate(ref tNode);
        //            break;
        //        case EH:
        //            tNode.BF = RH; lc.BF = LH;
        //            RRotate(ref tNode);
        //            shorter = false;
        //            break;
        //        case LH:
        //            Node rd = lc.Right;
        //            switch (rd.BF)
        //            {
        //                case RH:
        //                    tNode.BF = LH; lc.BF = EH; break;
        //                case EH:
        //                    tNode.BF = EH; lc.BF = EH; break;
        //                case LH:
        //                    tNode.BF = EH; lc.BF = RH; break;
        //            }
        //            lc.BF = EH;
        //            LRotate(ref tNode.Left);
        //            RRotate(ref tNode);
        //            break;
        //    }
        //}
        /// <summary>
        /// 删除用右平衡
        /// </summary>
        /// <param name="tNode"></param>
        /// <param name="shorter"></param>
        private void RightBalance(ref Node tNode, out bool shorter)
        {
            Node rc = tNode.Right;
            shorter = true;
            switch (rc.BF)
            {
                case EH:
                    tNode.BF = RH; rc.BF = LH;
                    LRotate(ref tNode);
                    shorter = false;
                    break;
                case RH:
                    tNode.BF = EH; rc.BF = EH;
                    LRotate(ref tNode);
                    break;
                case LH:
                    Node ld = rc.Right;
                    switch (ld.BF)
                    {
                        case EH:
                            tNode.BF = rc.BF = EH; break;
                        case LH:
                            tNode.BF = EH; rc.BF = RH; break;
                        case RH:
                            tNode.BF = LH; rc.BF = EH; break;
                    }
                    ld.BF = EH;
                    RRotate(ref tNode.Right);
                    LRotate(ref tNode);
                    break;
                //case LH:
                //    tNode.BF = rc.BF = EH;
                //    LRotate(ref tNode);
                //    break;
                //case EH:
                //    tNode.BF = LH; rc.BF = RH;
                //    shorter = false;
                //    break;
                //case RH:
                //    Node ld = rc.Left;
                //    switch (ld.BF)
                //    {
                //        case LH:
                //            tNode.BF = RH; rc.BF = EH; break;
                //        case EH:
                //            tNode.BF = EH; rc.BF = EH; break;
                //        case RH:
                //            tNode.BF = EH; rc.BF = LH; break;
                //    }
                //    ld.BF = EH;
                //    RRotate(ref tNode.Right);
                //    LRotate(ref tNode);
                //    break;
            }
        }
        /// <summary>
        ///插入用的右平衡
        /// </summary>
        /// <param name="tNode"></param>
        private void RightBalance(ref Node tNode)
        {
            Node rc = tNode.Right;
            switch (rc.BF)
            {
                //参看 AVL树图解.vsd RightBalance case A
                case RH:
                    tNode.BF = rc.BF = EH;
                    LRotate(ref tNode);
                    break;
                case LH:
                    Node ld = rc.Left;
                    switch (ld.BF)
                    {
                        //参看 AVL树图解.vsd RightBalance case B.1
                        case LH: tNode.BF = EH; rc.BF = RH; break;
                        //参看 AVL树图解.vsd RightBalance case B.2
                        case EH: tNode.BF = rc.BF = EH; break;
                        //参看 AVL树图解.vsd RightBalance case B.3
                        case RH: tNode.BF = LH; rc.BF = EH; break;
                    }
                    ld.BF = EH;
                    RRotate(ref tNode.Right);
                    LRotate(ref tNode);
                    break;
            }
        }



        /// <summary>
        /// 插入一结点
        /// </summary>
        /// <param name="tNode"></param>
        /// <param name="item"></param>
        /// <param name="taller"></param>
        /// <returns></returns>
        private bool Insert(ref Node tNode, T item, out bool taller)
        {
            if (tNode == null)
            {
                tNode = new BTreeSet<T>.Node();
                tNode.Item = item;
                taller = true;
            }
            else
            {
                if (m_comparer.Compare(item, tNode.Item) == 0)
                {
                    taller = false;
                    return false;
                }
                if (m_comparer.Compare(item, tNode.Item) < 0)
                {
                    if (!Insert(ref tNode.Left, item, out taller)) return false;
                    if (taller)
                    {
                        switch (tNode.BF)
                        {
                            //InsertNode.Case A.1
                            case LH:
                                LeftBalance(ref tNode); taller = false; break;
                            //InsertNode.Case A.2
                            case EH:
                                tNode.BF = LH; taller = true; break;
                            //InsertNode.Case A.3
                            case RH:
                                tNode.BF = EH; taller = false; break;
                        }
                    }
                }
                else
                {
                    if (!Insert(ref tNode.Right, item, out taller)) return false;
                    if (taller)
                    {
                        switch (tNode.BF)
                        {
                            //InsertNode.Case B.1
                            case LH:
                                tNode.BF = EH; taller = false; break;
                            //InsertNode.Case B.2
                            case EH:
                                tNode.BF = RH; taller = true; break;
                            //InsertNode.Case B.3
                            case RH:
                                RightBalance(ref tNode); taller = false; break;
                        }
                    }
                }
            }
            return true;
        }

        private bool Delete(ref Node tNode, T item, out bool shorter)
        {
            bool success = false;
            shorter = false;
            if (tNode != null)
            {
                if (m_comparer.Compare(item, tNode.Item) == 0)
                {
                    if (tNode.Left != null && tNode.Right != null)
                    {
                        Node q = tNode.Left;
                        Node r = q;
                        while (q != null)
                        {
                            r = q;// r 为前驱的父结点
                            q = q.Right;
                        }
                        //将数据和前驱交换过来 
                        T temp = tNode.Item;
                        tNode.Item = r.Item;
                        r.Item = temp;
                        //继续 递归删除 前驱结点
                        //置换后。由于删除结点比所有子树都大。因此会一真向右子树递归
                        success = Delete(ref tNode.Left, item, out shorter);
                        if (shorter)
                        {
                            switch (tNode.BF)
                            {
                                case LH: tNode.BF = EH; shorter = true; break;
                                case EH: tNode.BF = RH; shorter = false; break;
                                case RH: RightBalance(ref tNode, out shorter); break;//左子树短了。右平衡
                                //case RH: tNode.BF = EH; break;
                                //case EH: tNode.BF = LH; shorter = false; break;
                                //case LH: RightBalance(ref tNode, out shorter); break;
                            }
                        }
                    }
                    else
                    {
                        //实际的删除结点操作在这里
                        tNode = tNode.Left != null ? tNode.Left : tNode.Right;
                        success = true;
                        shorter = true;
                    }

                }

                else if (m_comparer.Compare(item, tNode.Item) < 0)
                {
                    success = Delete(ref tNode.Left, item, out shorter);
                    if (shorter)
                    {
                        switch (tNode.BF)
                        {
                            case LH: tNode.BF = EH; shorter = true; break;
                            case EH: tNode.BF = RH; shorter = false; break;
                            case RH: RightBalance(ref tNode, out shorter); break;//左子树短了。右平衡
                            //case RH: tNode.BF = EH; break;
                            //case EH: tNode.BF = LH; shorter = false; break;
                            //case LH: RightBalance(ref tNode, out shorter); break;
                        }
                    }
                }
                else //if (m_comparer.Compare(item, tNode.Item) > 0)
                {
                    success = Delete(ref tNode.Right, item, out shorter);
                    if (shorter)
                    {
                        switch (tNode.BF)
                        {
                            case RH: tNode.BF = EH; shorter = true; break;
                            case EH: tNode.BF = LH; shorter = false; break;
                            case LH: LeftBalance(ref tNode, out shorter); break;//右子树短了。左平衡
                            //case RH: LeftBalance(ref tNode, out shorter); break;
                            //case EH: tNode.BF = RH; shorter = false; break;
                            //case LH: tNode.BF = EH; break;
                        }
                    }
                }
            }
            return success;
        }


        //private bool Delete(ref Node tNode, T item, out bool shorter)
        //{
        //    bool success = false;
        //    if (item != null)
        //    {
        //        if (item.CompareTo(tNode.Item) == 0)
        //        {
        //            if (tNode.Right == null)//右子树 为空，重新接左子树
        //            {
        //                //Node q = tNode;
        //                tNode = tNode.Left;
        //                shorter = true;
        //            }
        //            else if (tNode.Left == null)//左子树 为空，重新接右子树
        //            {
        //                tNode = tNode.Right;
        //                shorter = true;
        //            }
        //            else
        //            {
        //                Node q = tNode; Node s = tNode.Left;//s  为要删除结点的前驱。q为s 的父结点
        //                while (s.Right != null)
        //                {
        //                    q = s; s = s.Right;
        //                }
        //                //用前驱替代。要删除的结点
        //                tNode.Item = s.Item;
        //                //删除 s 结点
        //                if (tNode == q)
        //                    q.Left = s.Left;
        //                else
        //                    q.Right = s.Left;

        //                //调整BF 
        //                if (q.BF == EH && s.BF == EH)
        //                {
        //                    q.BF = LH; shorter = false;
        //                }
        //                if (s.BF == EH && q.BF == LH)
        //                {
        //                    //LeftBalance(ref q);
        //                    LeftBalance(ref q, out shorter);
        //                }
        //                else
        //                {
        //                    shorter = true;
        //                }
        //            }
        //        }
        //        else
        //            if (item.CompareTo(tNode.Item) < 0)
        //            {
        //                success = Delete(ref tNode.Left, item, out shorter);
        //                if (shorter)
        //                {
        //                    //switch (tNode.BF)
        //                    //{
        //                    //  //  case EH:

        //                    //}
        //                }
        //            }
        //            else if (item.CompareTo(tNode.Item) > 0)
        //            {
        //                success = Delete(ref tNode.Right, item, out shorter);
        //                if (shorter)
        //                {
        //                    switch (tNode.BF)
        //                    {
        //                        case EH:
        //                            tNode.BF = LH; shorter = false; break;
        //                        case RH:
        //                            tNode.BF = EH;
        //                        case LH:
        //                            LeftBalance(ref tNode, out shorter);
        //                    }
        //                }
        //            }
        //    }
        //    shorter = true;
        //    return success;
        //}
        /// <summary>
        /// 中序遍历结果集
        /// </summary>
        /// <returns></returns>
        public string InOrderTraverse()
        {
            StringBuilder sb = new StringBuilder();
            if (m_root != null)
            {
                InOrderTraverse(m_root, ref sb);
                return sb.ToString();
            }
            return string.Empty;
        }
        private void InOrderTraverse(Node node, ref StringBuilder sb)
        {
            int count = 4;
            if (node != null)
            {
                --count;
                InOrderTraverse(node.Left, ref sb);
                ++count;
                sb.Append(node.Item.ToString() + " ");
                --count;
                InOrderTraverse(node.Right, ref sb);
                ++count;
            }
        }
        public string TraverseLayer()
        {
            int layer = 0;
            StringBuilder sb = new StringBuilder();
            if (m_root != null)
            {
                TraverseLayer(m_root, ref sb, layer);
            }
            return sb.ToString();
        }
        
        private void TraverseLayer(Node node, ref StringBuilder sb, int layer)
        {
            if (node == null) return;
            if (node.Right != null)
            {
                TraverseLayer(node.Right, ref sb, layer + 1);
            }
            for (int i = 0; i < layer; i++)
            {
                sb.Append(".   　　   ");
            }
            sb.AppendLine(node.Item.ToString() + string.Format("(BF={0})", node.BF));
            if (node.Left != null)
            {
                TraverseLayer(node.Left, ref sb, layer + 1);
            }
        }
        public string TraverseGraph()
        {
            StringBuilder sb = new StringBuilder();
            if (m_root != null)
            {
                int level = -1;
                bool endFlag = true;
                int[] flags = new int[100];
                bool rightFlag = false;//false means: Left, true means: Right
                TraverseGraph(m_root, ref sb, ref level, ref endFlag, flags, ref rightFlag);
            }
            return sb.ToString();
        }
        private void TraverseGraph(Node node, ref StringBuilder sb, ref int level, ref bool endFlag, int[] flags, ref bool rightFlag)
        {
            //int level = -1;
            //bool endFlag = true;
            //int[] flags = new int[100];
            //bool rightFlag = false;//false means: Left, true means: Right
            level++;
            if (node != null)
            {
                for (int i = 0; i < level; ++i)
                {
                    if (flags[i]==1)
                    {
                        sb.Append("│ ");
                    }
                    else
                    {
                        sb.Append("    ");
                    }
                }
                if (endFlag)
                {
                    if (!rightFlag)
                        sb.AppendLine(String.Format("└─L:{0} B:{1}", node.Item, node.BF));
                    else
                        sb.AppendLine(String.Format("└─R:{0} B:{1}", node.Item, node.BF));
                }
                else
                {
                    if (!rightFlag)
                        sb.AppendLine(String.Format("├─L:{0} B:{1}", node.Item, node.BF));
                    else
                        sb.AppendLine(String.Format("├─R:{0} B:{1}", node.Item, node.BF));
                }

                if (node.Left == null && node.Right == node || endFlag)
                    flags[level] = 1;
                else
                    flags[level] = 0;
                if (node.Right == null)
                    endFlag = true;
                else
                    endFlag = false;

                rightFlag = false;
                TraverseGraph(node.Left, ref sb, ref level, ref endFlag, flags, ref rightFlag);
                endFlag = true;
                rightFlag = true;
                TraverseGraph(node.Right, ref sb, ref level, ref endFlag, flags, ref rightFlag);

                --level;
            }
            // void AVLTree < Type >::Traverse_graph(AVLNode *ptr, ostream &out, int &level, bool &bEnd, int *bFlag, bool &bLR)const {
            ///*
            //static int level = -1;
            //static bool bEnd = true; //如果是最后一个结点
            //static int *bFlag = new int[100];
            //static bool bLR = false; // false means: Left, true means: Right
            //*/
            //++level;
            ////bFlag[level] = 1;

            //if(ptr != NULL) {
            //   for(int i = 0; i < level; ++i) {
            //    if(bFlag[i])
            //     //printf("│ ");
            //     out<<"│ ";
            //    else
            //     //printf("    ");
            //     out<<"    ";
            //   }

            //   if(bEnd){
            //    if(!bLR)
            //     //printf("└─L:%d B:%d\n", ptr->data, ptr->balance);
            //     out<<"└─L:"<<ptr->data<<" B:"<<ptr->balance<<endl;
            //    else
            //     //printf("└─R:%d B:%d\n", ptr->data, ptr->balance);
            //     out<<"└─R:"<<ptr->data<<" B:"<<ptr->balance<<endl;
            //   }
            //   else {
            //    if(!bLR)
            //     //printf("├─L:%d B:%d\n", ptr->data, ptr->balance);
            //     out<<"├─L:"<<ptr->data<<" B:"<<ptr->balance<<endl;
            //    else
            //     //printf("├─R:%d B:%d\n", ptr->data, ptr->balance);
            //     out<<"├─R:"<<ptr->data<<" B:"<<ptr->balance<<endl;
            //   }

            //   if((ptr->left == NULL && ptr->right == NULL) || bEnd)
            //    bFlag[level] = 0;
            //   else 
            //    bFlag[level] = 1;

            //   if(ptr->right == NULL)
            //    bEnd = true;
            //   else
            //    bEnd = false;

            //   bLR = false;
            //   Traverse_graph(ptr->left, out, level, bEnd, bFlag, bLR);

            //   bEnd = true;
            //   bLR = true;
            //   Traverse_graph(ptr->right, out, level, bEnd, bFlag, bLR);
            //}

            ////delete bFlag[level];
            //--level;
            ////bEnd = false;
            //}
        }

        #region ICollection<T> 成员

        void ICollection<T>.Add(T item)
        {
            Add(item);
        }

        public void Clear()
        {
            this.m_root = null;
            this.m_count = 0;
        }

        public bool Contains(T item)
        {
            if (item == null)
            {
                throw new ArgumentNullException();
            }

            Node p = this.m_root;
            while (p != null)
            {
                int c = m_comparer.Compare(item, p.Item);

                if (c < 0)
                {
                    p = p.Left;
                }
                else if (c > 0)
                {
                    p = p.Right;
                }
                else
                {
                    return true;
                }
            }
            return false;
        }

        public void CopyTo(T[] array, int index)
        {
            if (array == null)
            {
                throw new ArgumentNullException();
            }

            if ((index < 0) || (index >= array.Length))
            {
                throw new ArgumentOutOfRangeException();
            }

            if ((array.Length - index) < this.m_count)
            {
                throw new ArgumentException();
            }

            Node p = this.m_root;

            if (p == null)
            {
                return;
            }
            Stack<Node> stack = new Stack<Node>();
            //非递归中序遍历
            while (p != null || stack.Count > 0)
            {
                if (p != null)
                {
                    stack.Push(p);
                    p = p.Left;
                }
                else
                {
                   p= stack.Pop();
                   array[index++] = p.Item;
                   p = p.Right;
                }
            }
        }

        public int Count
        {
            get { return this.m_count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        #endregion

        #region IEnumerable<T> 成员

        public IEnumerator<T> GetEnumerator()
        {
            Node p = this.m_root;

            if (p == null)
            {
                yield break;
            }
            Stack<Node> stack = new Stack<Node>();
            //非递归中序遍历
            while (p != null || stack.Count > 0)
            {
                if (p != null)
                {
                    stack.Push(p);
                    p = p.Left;
                }
                else
                {
                    p = stack.Pop();
                    yield return p.Item;
                    //array[index++] = p.Item;
                    p = p.Right;
                }
            }
        }

        #endregion

        #region IEnumerable 成员

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion
    }
}
